package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 2167. 移除所有载有违禁货物车厢所需的最少时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/11 16:18
 */
public class MinimumTime {


    public static void main(String[] args) {
        MinimumTime test = new MinimumTime();

        // 5
//        String str = "1100101";

        // 8
        String str = "1001010101";

        int i = test.minimumTime(str);
        System.out.println(i);
    }


    public int minimumTime(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        int sum = 0;
        int count = 0;
        int[] arr1 = new int[length];
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (c == '0') {
                count = 0;
                arr1[i] = sum;
                continue;
            }
            count++;
            arr1[i] = Math.min(i + 1, count * 2 + sum);
            if (i + 1 < length && chars[i + 1] == '0') {
                sum = arr1[i];
            }
        }
        sum = 0;
        int max = arr1[length - 1];
        for (int i = length - 1; i > 0; i--) {
            char c = chars[i];
            if (c == '0') {
                count = 0;
                continue;
            }
            count++;
            int v = Math.min(length - i, count * 2 + sum);
            max = Math.min(max, arr1[i - 1] + v);
            if (chars[i - 1] == '0') {
                sum = v;
            }
        }
        if (chars[0] == '1') {
            count++;
        }
        return Math.min(max, Math.min(length, count * 2 + sum));
    }

}
